package Prac;

import java.util.*;

public class P11_28 {

    TreeNode lca = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findNode(root,p,q);
        return lca;
    }

    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return false;
        }
        int left = findNode(root.left,p,q)?1:0;
        int right = findNode(root.right,p,q)?1:0;
        int mid = (root.val==p.val||root.val==q.val)?1:0;
        if(left+right+mid==2){
            lca = root;
            return true;
        }
        return left+right+mid>0;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if(root==null){
            return ret;
        }
        TreeNode cur = root;//当前遍历的节点
        TreeNode prev = null;//已经处理完的节点
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){//将cur压栈,并一直向左走
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();//此时cur是最左的节点
           if(cur.right==null||cur.right==prev){//cur没有右子树或者右子树已经遍历
               ret.add(cur.val);//将cur加入结果集
               prev = cur;//cur被处理完(即遍历完左右子树)
               cur = null;//cur置空,重新取栈顶值
           }else {
               stack.push(cur);//cur没有遍历完右子树,重新压栈
               cur = cur.right;//cur=右子树
           }
        }
        return ret;
    }

    StringBuilder sb = new StringBuilder();
    public String tree2str(TreeNode root) {
        if(root==null){
            return "";
        }
        sb.append(root.val);//先加入根节点
        if(root.left!=null){
            sb.append("(");
            tree2str(root.left);//放入左子树
            sb.append(")");
        }else if(root.right!=null){
            sb.append("()");//有右无左加()
        }
        if(root.right!=null){
            sb.append("(");
            tree2str(root.right);//右不为空加入右子树
            sb.append(")");
        }
        return sb.toString();
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if(root==null){
            return ret;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);//将根节点放入栈中
        while (!stack.isEmpty()){
            TreeNode top = stack.poll();//碰到根节点就出栈
            ret.add(top.val);
            if(top.right!=null){//先压栈右子树,因为栈是先入后出
                stack.push(top.right);
            }
            if(top.left!=null){//再压栈左子树
                stack.push(top.left);
            }
        }
        return ret;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if(root==null){
            return ret;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();//迭代中序遍历需要栈辅助
        TreeNode cur = root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){//一直走左子树
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();//左子树走完遍历根节点
            ret.add(cur.val);
            cur = cur.right;//右子树开始中序遍历
        }
        return ret;
    }

    public boolean isCompleteTree(TreeNode root) {
        if(root.left==null&&root.right==null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean second = false;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(!second){
                if(node.left!=null&&node.right!=null){
                    queue.offer(node.left);
                    queue.offer(node.right);
                }else if(node.left==null&&node.right!=null){
                    return false;
                }else if(node.left!=null){
                    queue.offer(node.left);
                    second = true;
                }else {
                    second = true;
                }
            }else {
                if(node.left!=null||node.right!=null){
                    return false;
                }
            }
        }
        return true;
    }
}
